/*
203. 移除链表元素
link:https://leetcode.cn/problems/remove-linked-list-elements/
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有
满足 Node.val == val 的节点，并返回 新的头节点 
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //法1：记录要删除节点的前一节点，
struct ListNode* removeElements1(struct ListNode* head, int val) {
    //处理头节点就是要删除的节点
    while(head != NULL && head->val == val) 
        head = head->next;
    //处理空链表以及删除之后为空的链表
    if(NULL == head) 
        return head;
    struct ListNode* pcur = head;
    while(pcur->next != NULL){
        //找到pcur->next->val = val 删除节点
        if(pcur->next->val == val){
            pcur->next = pcur->next->next;
        }
        //没找到继续遍历
        else{
            pcur = pcur->next;
        }
    }
    return head;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //法2:把不等于val的尾插到新链表
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* newhead, *newtail;
    newhead = newtail = NULL;
    struct ListNode* pcur = head;
    while(pcur){
        //不等于val尾插
        if(pcur->val != val){
            //链表为空
            if(newhead == NULL){
                newhead = newtail = pcur;
            }else{
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newtail){
        newtail->next = NULL;
    }
    return newhead;
}